#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=100010;
struct Node{
	int next;
	int dat;
	int order;
	int ad;
}node[maxn];
bool cmp(Node a,Node b){
	return a.order<b.order;
}
int main(void){
	int st,n,num;
	scanf("%d%d%d",&st,&n,&num);
	for(int i=0;i<maxn;i++)
	    node[i].order=maxn+1;
	for(int i=0;i<n;i++){
		int a,d,ne;
		scanf("%d%d%d",&a,&d,&ne);
		node[a].ad=a;
		node[a].dat=d;
		node[a].next=ne;
	}
	int temp=st;
	int c=0;
	while(temp!=-1){
		node[temp].order=c++;
		temp=node[temp].next;
	}
	sort(node,node+maxn,cmp);
	vector<Node> v1;
	int ind=0;
	while(ind+num<c){
		for(int i=ind+num-1;i>=ind;i--)
		    v1.insert(v1.end(),node[i]);
		ind+=num;
	}
	for(int i=ind;i<c;i++){
		v1.insert(v1.end(),node[i]);
	}
	int i;
	for(i=0;i<v1.size()-1;i++)
	    printf("%05d %d %05d\n",v1[i].ad,v1[i].dat,v1[i+1].ad);
	printf("%05d %d -1\n",v1[i].ad,v1[i].dat);
	return 0;
}